Leetcode刷题记录(Java)

发表于 | 更新于: | 分类于
Problem 2 Add Two Numbers/Problem 3 Longest Substring Without Repeating Characters/Problem 5 Longest Palindromic Substring/Problem 15 3Sum/Problem 22 Generate Parentheses/Problem 24 Swap Nodes in Pairs/Problem 29 Divide Two Integers/Problem 31 Next Permutation/Problem 39 Combination Sum/Problem 40 Combination Sum II/Problem 46 Permutations

Problem 2 Add Two Numbers
KlwH1A.png
求两个由链表组成的数的和

主要思路:
两数相加问题自然是每位相加,如果出现进位问题则带入下一位计算.

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode p1 = l1,p2=l2;
        int sum = 0;
        ListNode cur = dummy;
        while (p1!=null||p2!=null){
            if (p1!=null){
                sum+=p1.val;
                p1 = p1.next;
            }
            if (p2!=null){
                sum+=p2.val;
                p2 = p2.next;
            }
            cur.next = new ListNode(sum%10);
            sum /= 10;
            cur = cur.next;
        }
        if (sum==1){
            cur.next = new ListNode(1);
        }
        return dummy.next;
    }
}

代码说明:
该题思路非常清晰,主要是一些处理做法需要注意:

  • 在遇到需要新创建链表的问题时可以先创建一个dummy结点用作头结点,最后返回的时候返回dummy.next
  • 在求两数相加问题时,各位数相加取模,进位取除

Problem 3 Longest Substring Without Repeating Characters
KlslGD.png
找寻字符串中不含有不相同字符的最长字串

主要思路:
这个题目可以采用滑动窗口的做法,创建一个Hashset,如果当前字符不在set内就添加进去,如果当前字符已经在set中,则滑动窗口的前半部分不断缩小,直到将之前存在的相同字符移除

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s.length() == 0)
            return 0;
        int start = 0;
        int end = 0;
        int max = 0;
        HashSet<Character> set = new HashSet<>();
        while (start<s.length()&&end<s.length()){
            if (!set.contains(s.charAt(end))){
                set.add(s.charAt(end));
                max = Math.max(max,end-start+1);
                end++;
            }else {
                set.remove(s.charAt(start));
                start++;
            }
        }
        return max;
    }
}

代码说明:
以abcdcef为例,开始start和end都是0,start用于控制窗口的左边界,end用于控制窗口的右边界,set分别添加a,b,c,d.end从0增加至4,max也从0增加至4,而start一直为0.此时碰上了相同的字符c,则窗口开始缩小,start从0开始将set中的字符去除,直到c被移除,此时start为3,由于此时set中已经不存在c了,所以第二个c被添加进set,继续循环.

Problem 5 Longest Palindromic Substring
KlWsht.png
寻找最长的回文子串

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public String longestPalindrome(String s) {
        if (s==null||s.length()==0)
            return s;
        String res = "";
        boolean[][] dp = new boolean[s.length()][s.length()];
        int max = 0;
        for (int j=0;j<s.length();j++){
            for (int i=0;i<=j;i++){
                dp[i][j] = s.charAt(i)==s.charAt(j)&&((j-i<=2)||dp[i+1][j-1]);
                if (dp[i][j]){
                    if (j-i+1>max){
                        max = j-i+1;
                        res = s.substring(i,j+1);
                    }
                }
            }
        }
        return res;
    }
}

代码说明:
以babad为例,j在此处代表的含义是最远的距离,而i代表开始的点.
主要对dp二维数组进行分析,以j=4为例,i=0,如果此时s.charAt(j)==s.charAt(i)则需要判断他们中间的字符串是不是回文,也就是[1,3]是不是回文,也就是条件中判断dp[i+1][j-1]的条件,而j-i<=2,是因为如果两个字符相差距离不到2的话则最多只有3个字符,只要首位两个相同,中间字符可以为任意字符,所以在字符相同的情况下如果两者下标距离小于2,则必然能组成回文.

⭐Problem 15 3Sum
K1FkM6.png
寻找三元组的和与target相等的所有三元组

主要思路:
3Sum和2Sum思路相类似,就是先排序,固定住一个值,然后利用两个指针分别从头部和尾部逼近,利用二分搜索原理,如果和比target小则移动头部,比target大则移动尾部.

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        for (int i=0;i<nums.length-2;i++){
            if (i>0&&nums[i]==nums[i-1])
                continue;
            int low = i+1,high = nums.length-1,sum = 0-nums[i];
            while (low<high){
                if (nums[low]+nums[high]==sum){
                    res.add(Arrays.asList(nums[i],nums[low],nums[high]));
                    while (low<high&&nums[low]==nums[low+1])
                        low++;
                    while (low<high&&nums[high]==nums[high-1])
                        high--;
                    low++;
                    high--;
                }else if (nums[low]+nums[high]<sum)
                    low++;
                else 
                    high--;
            }
        }
        return res;
    }
}

代码说明:
代码本身思路比较清晰,但是有些细节需要注意:

  • i>0&&nums[i]==nums[i-1]这个判断条件用于判断新的头部是否和之前的头部相同,例如1,1,2,3中如果第一个1已经当作固定值的话,第二个1就是无意义的固定值,所以需要跳过,这点在循环中同理,需要判断

Problem 22 Generate Parentheses
K1VFte.png
生成一对括号

主要思路:
利用DFS进行解答,遵循几个原则

  • 如果左右括号剩余数量都是0则添加
  • 如果左括号数大于右括号数则不符合条件
  • 如果剩余还有左括号则添加(
  • 如果剩余还有右括号则添加)

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> list = new ArrayList<>();
        DFS(n,n,"",list);
        return list;
    }
    public void DFS(int left,int right,String temp,List<String> list){
        if (left>right)
            return;
        if (left==0&&right==0)
            list.add(temp.toString());
        else {
            if (left>0)
                DFS(left-1,right,temp+"(",list);
            if (right>0)
                DFS(left,right-1,temp+")",list);
        }
    }
}

Problem 24 Swap Nodes in Pairs
K1ZiD0.png
以一对为单位交换结点顺序

主要思路:
根据题意可知至少需要一个指针指向头结点的下两个结点,这题的关键就在于组织好指针关系.

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head==null||head.next==null)
            return head;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode l1 = dummy;
        ListNode l2 = head;
        while (l2!=null&&l2.next!=null){
            ListNode nextStar = l2.next.next;
            l1.next = l2.next;
            l2.next.next = l2;
            l2.next = nextStar;
            l1 = l2;
            l2 = l2.next;
        }
        return dummy.next;
    }
}

代码说明:

  • dummy.next = head; dummy:0->1->2->3->4
  • ListNode l1 = dummy; dummy:0->1->2->3->4 l1:0->1->2->3->4
  • ListNode l2 = head; dummy:0->1->2->3->4 l1:0->1->2->3->4 l2:1->2->3->4
  • ListNode nextStar = l2.next.next; dummy:0->1->2->3->4 l1:0->1->2->3->4 l2:1->2->3->4
  • l1.next = l2.next; dummy:0->2->3->4 l1:0->2->3->4 l2:1->2->3->4
  • l2.next.next = l2; dummy:0->2->1->2->1 l1:0->2->1->2 l2:1->2->1->2
  • l2.next = nextStar; dummy:0->2->1->3->4 l1:0->2->1->3 l2:1->3->4
  • l1 = l2; dummy:0->2->1->3->4 l1:1->3->4 l2:1->3->4
  • l2 = l2.next; dummy:0->2->1->3->4 l1:1->3->4 l2:3->4
    l1=l2这行相当于把l1重新置为头结点,而l2=l2.next相当于将l2重新置为新的配对结点中的第一个结点.

Problem 29 Divide Two Integers
K1Nxcq.png
实现两数相除操作,同时需要处理溢出情况

主要思路:
相除但不能使用内置实现的话自然考虑被除数减去除数,但是不能用传统直接循环相减的方法,这样遇到一个大数除以1的情况会出现超时.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int divide(int dividend, int divisor) {
        if (dividend==0)
            return 0;
        boolean flag = dividend > 0 && divisor > 0 || dividend < 0 && divisor < 0;
        long ldividend = Math.abs((long)dividend);
        long ldivisor = Math.abs((long)divisor);
        long lres = divide(ldividend,ldivisor);
        int res = 0;
        if (lres>Integer.MAX_VALUE){
            res = flag?Integer.MAX_VALUE:Integer.MIN_VALUE;
        }else
            res = flag?(int)lres:-(int)lres;
        return res;
    }
    public long divide(long ldividend,long ldivisor){
        if (ldividend<ldivisor)
            return 0;
        long sum = ldivisor;
        long multiple = 1;
        while ((sum+sum)<=ldividend){
            sum+=sum;
            multiple+=multiple;
        }
        return multiple+divide(ldividend-sum,ldivisor);
    }
}

代码说明:
上面的代码使用了递归操作,其核心部分在于循环,使用sum+sum的方法使得除数快速逼近被除数.而multiple也是翻倍递增.当被除数已经没有2倍除数大的情况下就进入递归,递归的被除数就是剩下的数.以9/3
为例,最初是3+3<9,此时multiple=2,之后进入递归(9-6,3),3+3>3,multiple=1,之后进入递归(0,3),满足退出递归条件.所以结果是multiple之和为3.

⭐Problem 31 Next Permutation
K1dklR.png
求全排列的下一个字符串

主要思路:
以127431为例,其全排列输出的下一个字符串为131247,其逻辑为先找到升序状态下的倒数第二个数,也就是说如果一个字符串序列为全降序排列,其必然是该全排列的最大值,按照题意将其整体翻转即可.在127这个升序序列中倒数第二个数为2,之后就是以2为起点,寻找比其大的数中最小的数,与2交换,在例子中就是3和2交换,形成137421,最后以3之后的数为起点翻转得到结果.总结起来为:

  • 找到升序序列中倒数第二个数
  • 找到上数后比其大的最小数
  • 交换两数
  • 从交换之后+1为起点翻转

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
    public void nextPermutation(int[] nums) {
        if (nums.length!=0){
            int secondBiggestInAsc = -1;
            for (int i=nums.length-2;i>=0;i--){
                if (nums[i]<nums[i+1]){
                    secondBiggestInAsc = i;
                    break;
                }
            }
            int biggerIndex = 0;
            if (secondBiggestInAsc==-1){
                reverse(nums,0,nums.length-1);
                return;
            }else {
                int max = Integer.MAX_VALUE;
                for (int i=secondBiggestInAsc;i<nums.length;i++){
                    if (nums[i]>nums[secondBiggestInAsc]&&nums[i]<=max){
                        max = nums[i];
                        biggerIndex = i;
                    }
                }
            }
            int temp = nums[secondBiggestInAsc];
            nums[secondBiggestInAsc] = nums[biggerIndex];
            nums[biggerIndex] = temp;
            reverse(nums,secondBiggestInAsc+1,nums.length-1);
        }
    }
    public void reverse(int[] nums,int start,int end){
        while (start<end){
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }
}

Problem 39 Combination Sum
K1ghdA.png
找出所有属于候选值中的数据之和与给定值相等的数组

主要思路:
该题使用回溯法解决,回溯法的关键是状态的更新和状态的取消.

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        if (candidates==null||candidates.length==0)
            return res;
        helper(res,new ArrayList<>(),candidates,target,0);
        return res;
    }
    public void helper(List<List<Integer>> res,List<Integer> list,int[] candidates,int target,int start){
        if (target<0)
            return;
        if (target==0){
            res.add(new ArrayList<>(list));
            return;
        }
        for (int i=start;i<candidates.length;i++){
            list.add(candidates[i]);
            helper(res,list,candidates,target-candidates[i],i);
            list.remove(list.size()-1);
        }
    }
}

代码说明:
以题例中的candidates=[2,3,6,7],以及target=7为例,由于题目中说明可以单个元素重复使用,所以从index=0处开始

  • list:2
  • list:2,2
  • list:2,2,2
  • list:2,2,2,2 此时target<0,故退出,同时list变成2,2,2,循环进入第二轮,此时3被加入
  • list:2,2,2,3 此时target<0,故退出,同时list变成2,2,2,循环进入第三轮,此时6被加入
  • list:2,2,2,6 此时target<0,故退出,同时list变成2,2,2,循环进入第四轮,此时7被加入
  • list:2,2,2,7 此时target<0,故退出,同时list变成2,2,2,循环结束,递归退出之后list继续remove最后一个元素,list变为2,2
  • list:2,2,3
  • list:2,2,3,3 …

Problem 40 Combination Sum II
K1obQI.png
条件与上一题相同,只是每个元素只能使用一次.

主要思路:
凡是涉及到元素只能使用一次的场合均要使用排序加上去重.

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(candidates);
        if (candidates==null||candidates.length==0)
            return res;
        helper(res,new ArrayList<>(),candidates,target,0);
        return res;
    }
    public void helper(List<List<Integer>> res,List<Integer> list,int[] candidates,int target,int start){
        if (target<0)
            return;
        if (target==0){
            res.add(new ArrayList<>(list));
            return;
        }
        for (int i=start;i<candidates.length;i++){
            if(i!=start&&candidates[i]==candidates[i-1])
                continue;
            list.add(candidates[i]);
            helper(res,list,candidates,target-candidates[i],i+1);
            list.remove(list.size()-1);
        }
    }
}

⭐Problem 46 Permutations
K17SHK.png
全排列问题

主要思路:
全排列问题使用回溯法解决,在使用回溯法时需要注意结束条件,状态更改和状态消除.

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums==null||nums.length==0)
            return res;
        Integer[] numsInt = new Integer[nums.length];
        for (int i=0;i<nums.length;i++){
            numsInt[i] = nums[i];
        }
        helper(numsInt,0,res);
        return res;
    }
    public void helper(Integer[] nums,int start,List<List<Integer>> res){
        if (start==nums.length-1)
            res.add(new ArrayList<>(Arrays.asList(nums)));
        for (int i=start;i<nums.length;i++){
            int temp = nums[start];
            nums[start] = nums[i];
            nums[i] = temp;
            helper(nums,start+1,res);
            temp = nums[start];
            nums[start] = nums[i];
            nums[i] = temp;
        }
    }
}

代码说明:
K1bQ6s.png
通过上面这张图就能看出全排列的实现方式,就是固定位置交换.

  • 1和1交换,进入递归,2和2交换,进入递归,此时满足start==nums.length-1,所以添加123,3和3交换,进入递归,不满足循环,故跳出递归,start=2,i=2,3和3交换,继续不满足循环,跳出递归start=1,i=1,也就是2和2交换,继续循环,此时i++为2,也就是说下一次循环就是2和3交换.
  • 交换后满足start==nums.length-1,所以添加132,进入循环2和2交换,进入递归,不满足循环,跳出递归,start=2,i=2,2和2交换,继续不满足循环,跳出递归,start=1,i=2,所以2和3交换,也就是状态消除的过程.继续循环,由于i++不小于nums.length,所以不满足循环,跳出递归,start=0,i=0,继续循环,也就是1和2的交换,形成213.
  • …